package day07;

// 合法括号序列判断

// 修改版
// 使用栈结构来存储左括号，并与右括号进行匹配出栈

import java.util.Stack;

public class Main2 {
    public boolean chkParenthesis(String A, int n) {
        // 一定不要忘记进行条件判断
        if(n%2 != 0) {
            // 如果括号是单数，根本没有判断的必要
            return false;
        }

        // 栈是先进后出，括号是最近的匹配
        Stack<Character> stack = new Stack<>();

        // 进行遍历：入栈和匹配出栈操作
        for (int i = 0; i < A.length(); i++) {
            char ch = A.charAt(i);
            if(ch == '(') {
                // 左括号进行入栈操作
                stack.push(ch);
            } else if(ch == ')'){
                // 如果是右括号
                // 栈不为空时才可以进行出栈操作，一旦栈为空就是false
                if(stack.isEmpty()) {
                    return false;
                }
                // 不空就进行弹出操作
                stack.pop();
            } else {
                // 除了（）之外的字符
                return false;
            }
        }
        // 最后判断的条件：匹配完成后栈应该是空
        return stack.isEmpty();
    }
}




//// 最近的进行匹配
//
//public class Main2 {
//
//    // 部分正确
//    public boolean chkParenthesis(String A, int n) {
//        // write code here
//
//        int left = 0;
//        int right = 0;
//        int lindex =0;
//        int rindex = 0;
//        for (int i = 0; i < n; i++) {
//            // 好像是进行分情况：
//            // 左括号多、右括号多、左右一样、存在其他字符、)(前后
//            if(A.charAt(i) != '(' || A.charAt(i)!=')') {
//                return false;
//            }
//            if(A.charAt(0)==')') {
//                return false;
//            }
//            // 说明是括号，进行判断
//            if(A.charAt(i)=='(') {
//                left++;
//                lindex +=i;
//            } else {
//                right++;
//                rindex += i;
//            }
//        }
//        if(left!=right) {
//            return false;
//        } else {
//            if(lindex<rindex) {
//                return true;
//            } else {
//                return false;
//            }
//        }
//    }
//}
